package com.ljy.my_study.leetcode.单词搜索II;

import java.util.*;

/**
 * @author lijunying
 * @date 2021/9/16 9:59
 */
public class TestMain {

//    给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。
//
//    单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
//
//             
//
//    示例 1：
//
//
//    输入：board = [['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']], words = ['oath','pea','eat','rain']
//    输出：['eat','oath']
//    示例 2：
//
//
//    输入：board = [['a','b'],['c','d']], words = ['abcb']
//    输出：[]
//             
//
//    提示：
//
//    m == board.length
//    n == board[i].length
//1 <= m, n <= 12
//    board[i][j] 是一个小写英文字母
//1 <= words.length <= 3 * 104
//            1 <= words[i].length <= 10
//    words[i] 由小写英文字母组成
//    words 中的所有字符串互不相同
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/word-search-ii
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        char[][] board= {{'o','a','a','n'}, {'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}};
        String[] word={"oath","pea","eat","rain"};
        System.out.println(new TestMain().findWords(board,word));
    }

//    字典树+dfs
    public List<String> findWords(char[][] board, String[] words) {
        int xLen=board.length;
        int yLen=board[0].length;
        boolean[][] visited=new boolean[xLen][yLen];
        Map<Character,Trie> trieMap= createTries(words);
        Set<String> set=new LinkedHashSet<>();
        for(int i=0;i<xLen;i++){
            for(int j=0;j<yLen;j++){
                Trie trie=trieMap.get(board[i][j]);
                if(trie==null){
                    continue;
                }
                visited[i][j]=true;
                if(trie.word!=null){
                    set.add(trie.word);
                }
                dfs(board,i,j,visited,trie.next,set);
                visited[i][j]=false;
            }
        }
        return new ArrayList<>(set);
    }

    private int[][] directions={{0,1},{1,0},{0,-1},{-1,0}};

    private void dfs(char[][] board,int x,int y,boolean[][] visited,Map<Character,Trie> trieMap,Set<String> result){
        int xLen=board.length;
        int yLen=board[0].length;
        for(int i=0;i<directions.length;i++){
            int newX=x+directions[i][0];
            int newY=y+directions[i][1];
            if(newX<0||newX>=xLen){
                continue;
            }
            if(newY<0||newY>=yLen){
                continue;
            }
            if(visited[newX][newY]){
                continue;
            }
            Trie trie=trieMap.get(board[newX][newY]);
            if(trie==null){
                continue;
            }
            if(trie.word!=null){
                result.add(trie.word);
            }
            if(trie.next.isEmpty()){
                continue;
            }
            visited[newX][newY]=true;
            dfs(board,newX,newY,visited,trie.next,result);
            visited[newX][newY]=false;
        }
    }

    private Map<Character,Trie> createTries(String[] words){
        Map<Character,Trie> map=new HashMap<>();
        for(String w:words){
            int len=w.length();
            Map<Character,Trie> next=map;
            Trie trie=null;
            for(int i=0;i<len;i++){
                char c=w.charAt(i);
                Trie nextTrie= next.getOrDefault(c,new Trie(c));
                next.put(c,nextTrie);
                next=nextTrie.next;
                if(i==len-1){
                    nextTrie.word=w;
                }
            }
        }
        return map;
    }

    public static class Trie{
        public char c;
        public Map<Character,Trie> next;
        public String word;

        public Trie(char c){
            this.c=c;
            this.next=new HashMap<>();
        }
    }
}
